In many computing systems, low-level instruction code is used as an intermediary between the hardware components of the computing system and the operating software and other high-level software executing on the computing system. In some computer systems, this low-level instruction code is known as the Basic Input and Output System (“BIOS”). The BIOS provides a set of software routines that allow high-level software to interact with the hardware components of the computing system using standard calls.
Because of limitations of the BIOS in many PC-compatible computers, a new firmware architecture for booting the computer and for intermediating the communication between the operating system and the hardware has been created. The new architecture is defined via a set of specifications. One of the specifications is called the Extensible Firmware Interface (“EFI”) Specification and is available from INTEL CORPORATION. The original EFI Specification from INTEL CORPORATION is also being extended by the Unified Extensible Firmware Interface Forum (“UEFI”).
The EFI Specification describes an interface between the operating system and the system firmware. In particular, the Specification defines the interface that platform firmware must implement and the interface that the operating system may use in booting. How the firmware implements the interface is left up to the manufacturer of the firmware. The EFI Specification provides mechanisms for EFI drivers to communicate with each other, and the EFI core provides functions such as allocation of memory, creating events, setting the clock, and many others. This is accomplished through a formal and complete abstract specification of the software-visible interface presented to the operating system by the platform and the firmware.
Additional details regarding the EFI and UEFI firmware architecture are defined by the group of specifications called INTEL Platform Innovation Framework for EFI (“the Framework”), which are available from INTEL CORPORATION. Unlike the EFI Specification, which focuses only on programmatic interfaces for the interactions between the operating system and system firmware, the Framework defines programmatic interfaces for performing the full range of operations that are required to initialize the platform from power on through transfer of control to the operating system.
The Framework defines two major execution phases: Pre-EFI Initialization (“PEI”) and the Driver Execution Environment (“DXE”). PEI includes the minimum amount of program code needed to perform basic platform initialization and is executed from non-volatile memory. When PEI has completed its initialization, including the initialization of main memory, control passes to the DXE, which performs higher-level platform initialization and diagnostic functions. Because PEI is executed before memory initialization, very limited memory resources are available during this phase. No global variables or procedures for de-allocating memory are available during PEI.
Pre-EFI Initialization modules (“PEIMs”) are specialized drivers that are executed during PEI. PEIMs are generally utilized to perform the actual hardware initialization that takes place during PEI. Communication between PEIMs is very difficult during the limited memory PEI phase. In order to enable such communication, the PEI phase provides mechanisms for PEIMs to locate and invoke interfaces from other PEIMs. This mechanism is called a PEIM-to-PEIM Interface (“PPI”). The PEI phase provides functions for installing, reinstalling, and locating PPIs. The PEI phase also provides a function through which a PEIM can register to receive a notification when a specified PPI is installed.
In order to implement functions for installing, reinstalling, and locating PPIs, PEI should maintain a PPI database for storing data identifying the installed PPIs. The Framework does not, however, define how the PPI database should be implemented. Implementation of a database in an extremely memory-limited environment where code is executed from non-volatile memory is very difficult. In particular, the data structures typically utilized for database implementation are unsuitable for use in a memory limited environment, such as the PEI. For instance, linked lists require a relatively large amount of space for storing the pointers that link the nodes in the list. Arrays also have their own drawbacks in a memory-limited environment. In particular, arrays are allocated in advance and have a fixed size. As a result, the allocated but unused portion of an array is wasted. Additionally, as utilization of an array grows, previous solutions typically allocate memory for a larger array, copy the data from the current array to the new array, and de-allocate the memory for the old array. However, in PEI there is no functionality provided for de-allocating memory. Accordingly, the use of an array in this manner is not possible in PEI.
It is with respect to these considerations and others that the various embodiments of the invention have been made.